package leetcode_core.leetcode_4;

import java.util.PriorityQueue;

/**
 * 功能描述
 *
 * @author: 张庭杰
 * @date: 2022年09月28日 21:42
 */
public class NthSuperUglyNumber {
    public int nthSuperUglyNumber(int n, int[] primes) {
        int[] ans = new int[n+1];
        PriorityQueue<int[]> pq = new PriorityQueue<>((o1,o2)->{return o1[0] - o2[0];});
        for (int prime : primes) {
            pq.offer(new int[]{1,prime,1});
        }
        int p = 1;
        while (p <= n){
            int[] tuple = pq.poll();
            int product = tuple[0];
            int prime = tuple[1];
            int index = tuple[2];
            if(ans[p-1] != product){
                ans[p++] = product;
            }
            pq.offer(new int[]{ans[index]*prime,prime,index+1});
        }
        return ans[n];
    }
}
